//1600.王位继承顺序
//https://leetcode.cn/problems/throne-inheritance/?envType=daily-question&envId=2024-04-07
class ThroneInheritance {
    string king; //当前国王
    unordered_map<string,vector<string>> kid; //继承人
    unordered_set<string> nexist;
public:
    ThroneInheritance(string kingName):king(kingName) {
        kid[kingName];
    }
    
    void birth(string parentName, string childName) {
        kid[parentName].push_back(childName);
    }
    
    void death(string name) {
        nexist.insert(name); //加入死亡名单
    }
    //遍历找继承人 包括子孙
    void dfs(string k,vector<string>& ret)
    {
        if(nexist.count(k) == 0) ret.push_back(k);
        if(kid.count(k) == 0) return;
        for(const auto& inh:kid[k]) dfs(inh,ret);
    }
    vector<string> getInheritanceOrder() {
        vector<string> ret;
        dfs(king,ret);
        return ret;
    }
};